rtk 1999

1999.1.2 (dopolni)

1. podnaloga

Iz vesolja pričakuješ signal nezemeljske civilizacije. Utemeljeno lahko pričakuješ, da bo sporočilo poslano v jeziku, ki uporablja angleško abecedo 26 malih črk in zadošča naslednjim pravilom:

• Sporočilo je sestavljeno zgolj iz zaporedja znakov a, b, c, d, . . . , z, ki sestavljajo besede, in iz presledkov med njimi (brez ločil).
• Zaporedni znaki se vselej razlikujejo (ni podvojenih znakov).
• Samoglasniki a, e, i, o, u se ne smejo stikati.
• Znak x je lahko le na koncu besede.

Naloga

Dopolni funkcijo pravo(niz), ki ugotovi, ali sporočilo ustreza tem pogojem. Mesto dopolnjevanja je označeno z ###.

def pravo(niz):
    '''Vrne True, če besedilo v niz ustreza vseh pogojem in False sicer.'''

    dovoljeni_znaki = 'abcdefghijklmn###'
    samoglasniki = ['a','e','i','o','u']
    prejsnji_znak = ''
    for znak in niz:
        if znak not in dovoljeni_znaki:
            return False
        if znak == prejsnji_znak:
            return False
        if znak in samoglasniki ### prejsnji_znak in samoglasniki:
            return False
        if ### == 'x' ###:
            return False
        ###
    return True

Vhodni podatki

Sporočilo v obliki niza.

Izhodni podatki

True, če niz ustreza vsem pravilom in False sicer.

Primer

>>> pravo('we live in same universe')
`True`

>>> pravo('can you hear us')
`False`

Uradna rešitev

def pravo(niz):
    '''Vrne True, če besedilo v niz ustreza vseh pogojem in False sicer.'''

    dovoljeni_znaki = 'abcdefghijklmnopqrstuvwxyz '
    samoglasniki = ['a','e','i','o','u']
    prejsnji_znak = ''
    for znak in niz:
        if znak not in dovoljeni_znaki:
            return False    # nedovoljen znak
        if znak == prejsnji_znak:
            return False    # podvojen znak
        if znak in samoglasniki and prejsnji_znak in samoglasniki:
            return False    # zaporedna samoglasnika
        if prejsnji_znak == 'x' and znak != ' ':
            return False    # x ni na koncu besede
        prejsnji_znak = znak
    return True

1999.1.3 (dopolni)

1. podnaloga

V besedilu iščemo besede, ki vsebujejo vsaj eno zvezdico ($*$). Izpišemo vsako besedo z zvezdico, poleg nje pa tudi njej sledečo besedo, ne glede na to, ali tudi sama vsebuje zvezdico ali ne.

Naloga

Dopolni funkcijo besede(niz), ki izvede opisano opravilo. Besede so ločene s presledki. Mesto dopolnjevanja je označeno z ###.

def besede(niz):
    '''Izpiše besede v katerih je vsaj ena zvezdica (*) in njihove naslednike'''

    vse_besede = niz.split(' ')
    vsebuje_zvezdico = False
    novo_besedilo = []
    for beseda in vse_besede:
        if vsebuje_zvezdico == True and ###:
            novo_besedilo.append(beseda)
        if '*' in beseda:
            ###
            novo_besedilo.append(beseda)
        else:
            vsebuje_zvezdico = False
    return ###

Vhodni podatki

Besedilo v obliki niza.

Izhodni podatki

Niz ustreznih besed, ločenih s presledki.

Primer

>>> besede('Dan*es je lepo vre*m*e.')
'Dan*es je vre*m*e.'

>>> besede('Ka*j s*i jedel da*nes?')
'Kaj si jedel danes?'

Uradna rešitev

def besede(niz):
    '''Izpiše besede v katerih je vsaj ena zvezdica (*) in njihove naslednike'''

    vse_besede = niz.split(' ')
    vsebuje_zvezdico = False
    novo_besedilo = []
    for beseda in vse_besede:
        if vsebuje_zvezdico == True and '*' not in beseda:
            novo_besedilo.append(beseda)
        if '*' in beseda:
            vsebuje_zvezdico = True
            novo_besedilo.append(beseda)
        else:
            vsebuje_zvezdico = False
    return ' '.join(novo_besedilo)

1999.1.4 (dopolni)

1. podnaloga

V državi Utopiji so ugotovili, da denar kvari ljudi, zato vsako leto izvedejo prerazporeditev bogastva. Vsako leto določijo, kolikšno je največje sprejemljivo premoženje. Za vsakega državljana popišejo, koliko premoženja ima; tistim, katerih premoženje presega največji dovoljeni znesek, vzamejo toliko, da mu ostane le še ta največji dovoljeni znesek. Največje sprejemljivo premoženje je določeno kot 150% povprečnega premoženja. Tako dobljeni denar razdelijo med najrevnejše državljane in to tako, da ima na koncu čim večje število najrevnejših državljanov enako in čim večje premoženje. Pri tem se vrstni red prebivalcev po bogastvu ne sme spremeniti: če je imel A prej vsaj toliko kot B, ima tudi po prerazporeditvi vsaj toliko kot B.

Naloga

Dopolni funkcijo bogastvo, ki bo to dosegla. Predpostavi, da je mogoče denar drobiti na poljubno majhne enote, ter da je seznam bogastva urejen naraščajoče. Pri računanju povprečja uporabi funkcijo int(), ki bo kot rezultat vrnila celo število. Mesto dopolnjevanja je označeno z ###.

def bogastvo(seznam):
    '''Enakomerno razporedi bogastvo med državljane.'''

    stevilo_drzavljanov = len(seznam)
    povprecje = int(###)

    najvecje_bogastvo = int(povprecje * 1.5)

    # odvzamemo bogastvo tistim, ki presegajo 150% povprečja
    bogastvo = 0
    for i in range(stevilo_drzavljanov):
        drzavljan = seznam[i]
        if drzavljan > najvecje_bogastvo:
            bogastvo += ###
            seznam[i] = najvecje_bogastvo

    # določimo število prejemnikov
    prejemniki = 0  # število prejemnikov
    vsota = 0    # vsota prvotnih premoženj prejemnikov bogastva
    zmanjka_bogastva = False
    while prejemniki + 1 < stevilo_drzavljanov and ###:
        # preverimo, če je bogastva dovolj, da ga razdelimo med vse ljudi pred
        # državljanom seznam[prejemniki]
        if vsota + bogastvo <= seznam[prejemniki] * prejemniki:
            zmanjka_bogastva = True
        else:
            vsota += seznam[prejemniki]
            prejemniki += 1

    # razdelimo bogastvo revnim
    if prejemniki > 0:
        novo_bogastvo = int((vsota + bogastvo) / prejemniki)

        for k in range(###):
            seznam[k] = novo_bogastvo
    return seznam

Vhodni podatki

Seznam po velikosti urejenih celih števil, kjer vsako število predstavlja bogastvo nekega državljana.

Omejitve vhodnih podatkov

• $1 \leq n \leq 10^6$
  $n$ = število državljanov

Izhodni podatki

Seznam po velikosti urejenih celih števil, ki predstavljajo novo bogastvo.

Primer

Vhod

>>>>[30,50,120,240,260]

Izhod

[80, 80, 120, 210, 210]

Komentar

Nekatere nesprejemljive prerazporeditve so [90, 70, 120, 210, 210] (ker bi se spremenil vrstni red — prvi na seznamu ima zdaj več kot drugi), [40, 110, 120, 210, 210] (vrstni red se sicer ohrani, vendar je najrevnejši tukaj en sam, pri najboljši prerazporeditvi pa imata najrevnejša dva enako premoženje), [60, 60, 160, 210, 210] (najrevnejša dva imata sicer zdaj enako premoženje, vendar bi lahko dobila več).

Uradna rešitev

def bogastvo(seznam):
    '''Enakomerno razporedi bogastvo med državljane.'''

    stevilo_drzavljanov = len(seznam)
    povprecje = int(sum(seznam) / stevilo_drzavljanov)

    najvecje_bogastvo = int(povprecje * 1.5)

    # odvzamemo bogastvo tistim, ki presegajo 150% povprečja
    bogastvo = 0
    for i in range(stevilo_drzavljanov):
        drzavljan = seznam[i]
        if drzavljan > najvecje_bogastvo:
            bogastvo += drzavljan - najvecje_bogastvo
            seznam[i] = najvecje_bogastvo

    # določimo število prejemnikov
    prejemniki = 0  # število prejemnikov
    vsota = 0    # vsota prvotnih premoženj prejemnikov bogastva
    zmanjka_bogastva = False
    while prejemniki + 1 < stevilo_drzavljanov and not zmanjka_bogastva:
        # preverimo, če je bogastva dovolj, da ga razdelimo med vse ljudi pred
        # državljanom seznam[prejemniki]
        if vsota + bogastvo <= seznam[prejemniki] * prejemniki:
            zmanjka_bogastva = True
        else:
            vsota += seznam[prejemniki]
            prejemniki += 1

    # razdelimo bogastvo revnim
    if prejemniki > 0:
        novo_bogastvo = int((vsota + bogastvo) / prejemniki)

        for k in range(prejemniki):
            seznam[k] = novo_bogastvo
    return seznam